package week10.Chapter12_优先队列与堆.PP项目;


import week10.Chapter12_优先队列与堆.Exp2.LinkedBinaryTree;
import week10.Chapter12_优先队列与堆.jsjf.HeapADT;
import week10.Chapter12_优先队列与堆.jsjf.HeapNode;
import week10.Chapter12_优先队列与堆.jsjf.exceptions.EmptyCollectionException;

/**
 * LinkedHeap implements a heap.
 *
 * @author Lewis and Chase
 * @version 4.0
 */
public class LinkedHeap<T> extends LinkedBinaryTree<T> implements HeapADT<T>
{
    public HeapNode<T> lastNode;

    public LinkedHeap()
    {
        super();
    }

    /**
     * Adds the specified element to this heap in the appropriate
     * position according to its key value.
     *
     * @param obj the element to be added to the heap
     */
    @Override
    public void addElement(T obj)
    {
        HeapNode<T> node = new HeapNode<T>(obj);

        if (root == null) {
            root=node;
        } else
        {
            HeapNode<T> nextParent = getNextParentAdd();
            if (nextParent.getLeft() == null) {
                nextParent.setLeft(node);
            } else {
                nextParent.setRight(node);
            }

            node.setParent(nextParent);
        }
        lastNode = node;
        modCount++;

        if (size() > 1)
            heapifyAdd();
    }

    /**
     * Returns the node that will be the parent of the new node
     *
     * @return the node that will be the parent of the new node
     */
    private HeapNode<T> getNextParentAdd()
    {
        HeapNode<T> result = lastNode;

        while ((result != root) && (result.getParent().getLeft() != result)) {
            result = result.getParent();
        }

        if (result != root) {
            if (result.getParent().getRight() == null) {
                result = result.getParent();
            } else
            {
                result = (HeapNode<T>)result.getParent().getRight();
                while (result.getLeft() != null) {
                    result = (HeapNode<T>)result.getLeft();
                }
            }
        } else {
            while (result.getLeft() != null) {
                result = (HeapNode<T>)result.getLeft();
            }
        }

        return result;
    }

    /**
     * Reorders this heap after adding a node.
     */
    private void heapifyAdd()
    {
        T temp;
        HeapNode<T> next = lastNode;

        temp = next.getElement();

        while ((next != root) &&
			(((Comparable)temp).compareTo(next.getParent().getElement()) < 0))
        {
            next.setElement(next.getParent().getElement());
            next = next.parent;
        }
        next.setElement(temp);
    }

    /**
     * Remove the element with the lowest value in this heap and
     * returns a reference to it. Throws an EmptyCollectionException
     * if the heap is empty.
     *
     * @return the element with the lowest value in this heap
     * @throws EmptyCollectionException if the heap is empty
     */
    @Override
    public T removeMin() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedHeap");

        T minElement =  root.getElement();

        if (size() == 1)
        {
            root = null;
            lastNode = null;
        }
        else
        {
            HeapNode<T> nextLast = getNewLastNode();
            if (lastNode.getParent().getLeft() == lastNode) {
                lastNode.getParent().setLeft(null);
            } else {
                lastNode.getParent().setRight(null);
            }

            ((HeapNode<T>)root).setElement(lastNode.getElement());
            lastNode = nextLast;
            heapifyRemove();
        }

        modCount++;

        return minElement;
    }

    /**
     * Reorders this heap after removing the root element.
     */
    private void heapifyRemove()
    {
        T temp;
        HeapNode<T> node = (HeapNode<T>)root;
        HeapNode<T> left = (HeapNode<T>)node.getLeft();
        HeapNode<T> right = (HeapNode<T>)node.getRight();
        HeapNode<T> next;

        if ((left == null) && (right == null)) {
            next = null;
        } else if (right == null) {
            next = left;
        } else if (((Comparable)left.getElement()).compareTo(right.getElement()) < 0) {
            next = left;
        } else {
            next = right;
        }

        temp = node.getElement();
        while ((next != null) &&
			(((Comparable)next.getElement()).compareTo(temp) < 0))
        {
            node.setElement(next.getElement());
            node = next;
            left = (HeapNode<T>)node.getLeft();
            right = (HeapNode<T>)node.getRight();

            if ((left == null) && (right == null)) {
                next = null;
            } else if (right == null) {
                next = left;
            } else if (((Comparable)left.getElement()).compareTo(right.getElement()) < 0) {
                next = left;
            } else {
                next = right;
            }
        }
        node.setElement(temp);
    }

    /**
     * Returns the node that will be the new last node after a remove.
     *
     * @return the node that willbe the new last node after a remove
     */
    private HeapNode<T> getNewLastNode()
    {
        HeapNode<T> result = lastNode;

        while ((result != root) && (result.getParent().getLeft() == result)) {
            result = result.getParent();
        }

        if (result != root) {
            result = (HeapNode<T>)result.getParent().getLeft();
        }

        while (result.getRight() != null) {
            result = (HeapNode<T>)result.getRight();
        }

        return result;
    }

    /**
     * Returns the element with the lowest value in this heap.
     * Throws an EmptyCollectionException if the heap is empty.
     *
     * @return the element with the lowest value in this heap
     * @throws EmptyCollectionException if the heap is empty
     */
    @Override
    public T findMin() throws EmptyCollectionException
    {
        if (isEmpty()) {
            throw new EmptyCollectionException("LinkedHeap");
        }

        return root.getElement();
    }

    public static void main(String[] args) {
        LinkedHeap linkedHeap = new LinkedHeap();
        linkedHeap.addElement(36);
        linkedHeap.addElement(30);
        linkedHeap.addElement(18);
        linkedHeap.addElement(40);
        linkedHeap.addElement(32);
        linkedHeap.addElement(45);
        linkedHeap.addElement(22);
        linkedHeap.addElement(50);
        System.out.println("测试findMin:  " + linkedHeap.findMin());
        System.out.println("打印" + linkedHeap);
        System.out.println("测试removeMin:  " + linkedHeap.removeMin());
        System.out.println("打印" + linkedHeap);
    }
}

